1. Field of the Invention
The present invention relates to information security technology for performing exponentiation operations, modular exponentiation operations, and elliptic curve exponentiation operations.
2. Related Art
The widespread use of electronic data transmission resulting from developments in computer and communications technology has led to the increasing application of such technology as secret communications and digital signatures.
A secret communication system allows communications to be conducted between related parties without the communicated content being revealed to third parties. A digital signature system enables the receiver to authenticate the communicated content and verify the sender.
Both of these systems employ a cryptosystem known as public key cryptography. Public key cryptography provides a convenient method for managing a large number of separate encryption keys and is considered indispensable for communications involving many users. According to this system different keys are used for encryption and decryption, the encryption key being public and the decryption key remaining secret.
The Discrete Logarithm Problem
The security in public key cryptography is based on the intractability of the discrete logarithm problem. Commonly used discrete logarithms included those over finite fields and elliptic curves.
The discrete logarithm problem over a finite field assumes that GF is a finite field, and b and y are elements of GF. The discrete logarithm problem for GF is then to determine a value x such that:bx=ywhere x is an integer (when it exists).
The discrete logarithm problem over an elliptic curve assumes that E is an elliptic curve defined over GF, G is a base point lying on E, and Y is a new point lying on E.
The discrete logarithm problem for GF is then to determine a value x such that:Y=x*Gwhere x is an integer (when it exists).
The symbol “*” represents the multiple addition of the base point lying on the elliptic curve. For example, x*G represents the addition of a base point G to itself x times, or:x*G=G+G+G+G+. . . +G
The discrete logarithm problem is employed in the security of public key cryptosystems because of the computational difficulties involved in determining the value of x with respect to a finite field GF(p) having a large number of bases. Related issues are discussed in detail in Neal Koblitz, A Course in Number Theory and Cryptography, Springer-Verlag, 1987.
Exponentiation and Elliptic Curve Exponentiation
When the discrete logarithm problem is used as the basis for security in public key cryptography, two types of arithmetic operations are employed, those being exponentiation and elliptic curve exponentiation.
A well known method of performing exponentiation and elliptic curve exponentiation is the binary method described by D. E. Knuth in Seminumerical Algorithms: The Art of Computer Programming, Volume Two (3rd ed., Reading, Mass.: Addison-Wesley, 1997, c.1969).
Known refinements to the standard binary algorithm include the small window method (also described in Knuth above) and the signed binary method (see F. Morain, J. Olivos, “Speeding up the computations on an elliptic curve using addition-subtraction chains,” in Theoretical Informatics and Applications, vol. 24, no. 6, 1990).
Further refinements to the signed binary method are disclosed in unexamined patent application publications 7-49769 and 2000-330470 filed in Japan.
Binary Method
The following is a description of the prior art binary method, using modular exponentiation as an example.
In order to calculate Ak using the binary method, a modular exponentiation result is obtained by performing (i) n−1 modular squarings and (ii) modular multiplications such that ki=1. In this calculation exponent k is represented in binary, giving kn−1 kn−2 . . . ki . . . k1 k0 where n>i≧0 and ki=0 or 1.
According to the binary method, the variable i, which is an index showing which bits to investigate, is initially assigned a value n−1 where k is represented in binary. Also, a variable X, which will ultimately store the modular exponentiation result, is assigned an initial value of 1. Modulus n represents the bit size when k is represented in binary.
The following steps are then repeatedly performed while subtracting 1 from the value of variable i per repetition until i=0 (i=n−1, n−2, . . . , 1, 0).    Step 1: X=X2 (modular square X and assign the result to X)    Step 2: X=X×A only when ki=1 (modular multiply X by A and assign the result to X)
When the repetitions have been completed, the resulting value Ak is stored in X.
Small Window Method
The following description relates to another prior art method, the small window method.
The first step in calculating Ak using this method is the same as the binary method: the variables X and i are assigned initial values of 1 and n−1, respectively. The equation m=2w−1 is then calculated where W is a window size, and a table based on A is formulated that includes A0, A1, . . . , Am−1. Here, A0, A1, . . . , Am−1 are calculated as follows.A0=AA1=A3. . .Am−1=A2m−1
Next, the binary expression ki of the exponent k is converted to k′i. Here, ki has a value of 0 or 1, and k′1 has a value of 0, 1, . . . m−1.
Taking a three-bit sequence kt+2, kt+1, kt (the value of kt+2, kt+1, kt each being 0 or 1) in the binary expression . . . ki ki−1 . . . k1 k0 of exponent k as an example, the three bits are expressed collectively as k′t. Thus, k′t=011=3 when kt+2=0, kt+1=1, kt=1. Although this example is described in terms of being a conversion process using a three-bit sequence, it is actually window size that is used to conduct the conversion.
Next, the following steps are performed while subtracting 1 from variable i per repetition until i=0 (i=n−1, n−2, . . . , 1, 0)    Step 1: X=X2 (modular square X and assign the result to X)    Step 2: X=X×Ak′i only when k′i ≠0 (modular multiply X by Ak′i and assign the result to X)
When the repetitions have been completed, the resulting value Ak is stored in X.
The small window method is a well-known means of performing high-speed modular exponentiation because it allows for a reduction in the number of modular multiplications in comparison to the binary method.
Other prior art methods will not be discussed here due to their similarity with the two methods given above; namely, they also determine the exponent and perform modular multiplication and modular squaring on the determined value of the exponent.
Exemplary Structure of a Modular Exponentiation Device
The following description relates to a known modular exponentiation device for performing modular exponentiation using the above prior art arithmetic operation methods.
The modular exponentiation device is composed of a general-purpose microprocessor CPU, a RAM, and other elements.
The CPU, in addition to executing controls, performs modular multiplication and modular squaring. The RAM stores computer programs, table data, and calculation results. The computer programs are for executing the above binary method or small window method, and the CPU performs the binary method or the small window method in accordance with the computer programs.
In this extremely simple structure the CPU performs all of the arithmetic operations. The processing speeds of this simple structure are slow as a result of there being no specialized control circuits or calculation circuits.
A Variation of the Modular Exponentiation Device
The structure of this variation is different from the known modular exponentiation device discussed above. Instead of a general-purpose CPU, the device described here employs a coprocessor to perform the modular exponentiation, the coprocessor being capable of executing a number of dedicated operations at high speed. Thus, in addition to the general-purpose microprocessor CPU, this modular exponentiation device is characterized by including a coprocessor for conducting dedicated arithmetic operations.
In this device the CPU notifies the coprocessor to commence the operations. The coprocessor includes a control unit for controlling the other element of the device, a calculation unit for performing the modular exponentiation, a table data storage unit of storing the various table data, and a calculation result storage unit for storing the calculation results.
The control unit selects from the table data storage unit the data to be used for calculations in the calculation unit and transfers the selected data to the calculation unit. The calculation unit performs modular squarings and modular multiplications using the table data selected by the control unit and the calculation results stored in the calculation result storage unit, and stores the results of the calculations in the calculation result storage unit.
As described above, the coprocessor includes elements for storing the table data and the calculation results. This structure is adopted because the internal memory of the coprocessor is able to access the data faster than the external RAM when the control unit requires the data.
The separation of the control unit and the calculation unit in this structure allows for the operations to be performed at high speed. However, it is necessary to provide a table data storage unit accessible by the calculation unit, thus requiring the coprocessor to have a large internal memory.
Also, since the coprocessor is responsible for all the computation processing, the function of the CPU is limited to notifying the coprocessor to initiate the operations. The CPU, therefore, plays no part in the modular exponentiation operations performed by the coprocessor.
A Further Variation of the Modular Exponentiation Device
The following description relates to a further variation of the modular exponentiation device. This device is composed of a general-purpose microprocessor CPU and a coprocessor for performing dedicated arithmetic operations. The coprocessor includes a control unit, two calculation units (first and second calculation units), a table data storage unit for storing table data, and a calculation result storage unit for storing calculation results. The coprocessor operates the two calculation units in parallel.
The control unit selects data to be used in the calculations performed in the first calculation unit from the table data storage unit, and transfers the data to the first calculation unit. The first calculation unit performs modular multiplications using the table data selected by the control unit and the calculation results stored in the calculation result storage unit, and stores the results of the calculations in the calculation result storage unit. The second calculation unit performs modular squarings on the calculation results stored in the calculation result storage unit, and stores the results of the calculations in the calculation result storage unit.
By separating the calculation unit into first and second calculation units and having the two calculation units operate in parallel, it is possible for this device to perform the operations even faster than the above modular exponentiation device. As in the above device, the coprocessor in this structure is responsible for all the computation processing, and the CPU is only required to notify the coprocessor to initiate the operations. Thus the CPU plays no part in the modular exponentiation operations performed by the coprocessor. Naturally, the fact of there being two calculation units necessitates an increase in coprocessor circuitry.
As demonstrated above, a modular exponentiation device that relies on the CPU to perform all the arithmetic operations is unable to achieve an adequate operating frequency, resulting in the slow performance of the modular exponentiation calculations. The operating frequency can be improved by introducing a coprocessor to perform dedicated operations, although the coprocessor then requires a large internal memory.
Using the binary method, which only requires a small memory capacity, instead of the small window method, which needs a voluminous table, helps to reduce the memory requirements. The problem now is the relative computational slowness of the binary method in comparison to the small window method.
The speed at which modular exponentiation is performed according to the binary method can be improved by operating two coprocessors in parallel, although this problematically requires a doubling of the coprocessor circuitry.